package main.Q201_300;

import java.util.*;

public class Q291_300 {
    public static void main(String[] args) {
        System.out.println("Question291：");
        System.out.println("Question292：Nim游戏");
        System.out.println("Question293：");
        System.out.println("Question294：");
        System.out.println("Question295：数据流的中位数");
        System.out.println("Question296：");
        System.out.println("Question297：二叉树的序列化与反序列化");
        System.out.println("Question298：");
        System.out.println("Question299：猜数字游戏");
        System.out.println("Question300：最长递增子序列");
    }
}

class Question292{
    public boolean canWinNim(int n) {
        if (n%4==0) return false;
        else return true;
    }
}

class Question295{
    PriorityQueue<Integer> smallMax,bigMin;
    public Question295() {
        smallMax=new PriorityQueue<>(new Comparator<Integer>() {//小于中值数据大根堆
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        bigMin=new PriorityQueue<>(new Comparator<Integer>() {//大于中值数据小根堆
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });
    }

    public void addNum(int num) {
        if (smallMax.isEmpty()||num<=smallMax.peek()) {
            smallMax.offer(num);
            if (bigMin.size()+1<smallMax.size()) bigMin.offer(smallMax.poll());
        }else {
            bigMin.offer(num);
            if (bigMin.size()>smallMax.size()) smallMax.offer(bigMin.poll());
        }
    }

    public double findMedian() {
        if (smallMax.size()>bigMin.size()) return smallMax.peek();
        return (smallMax.peek()+bigMin.peek())/2.0;
    }
}

class Question297{
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "null,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("null")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }
}

class Question299{
    public String getHint(String secret, String guess) {
        int bulls = 0;
        int[] cntS = new int[10];
        int[] cntG = new int[10];
        for (int i = 0; i < secret.length(); ++i) {
            if (secret.charAt(i) == guess.charAt(i)) {
                ++bulls;
            } else {
                ++cntS[secret.charAt(i) - '0'];
                ++cntG[guess.charAt(i) - '0'];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += Math.min(cntS[i], cntG[i]);
        }
        return Integer.toString(bulls) + "A" + Integer.toString(cows) + "B";
    }
}

class Question300{
    public int lengthOfLIS(int[] nums) {
        int result=0,length= nums.length;
        int[] dp=new int[length];
        for (int i=0;i<length;i++){//以i为递增序列的最后一位
            int max=0;
            for (int j=0;j<i;j++){//i之前数字中比i小的数字所组成的最长序列长度
                if (nums[j]<nums[i])
                    max=Math.max(max,dp[j]);
            }
            dp[i]=max+1;
            result=Math.max(result,dp[i]);
        }
        return result;
    }
}